home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / TimeSchedulerSplayPQ.h,v < prev    next >
Text File  |  1989-03-22  |  4KB  |  193 lines
  1. head     3.3;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 3.3
  10. date     89.03.22.14.52.50;  author grunwald;  state Exp;
  11. branches ;
  12. next     3.2;
  13.  
  14. 3.2
  15. date     89.02.20.15.38.08;  author grunwald;  state Exp;
  16. branches ;
  17. next     ;
  18.  
  19.  
  20. desc
  21. @@
  22.  
  23.  
  24. 3.3
  25. log
  26. @*** empty log message ***
  27. @
  28. text
  29. @// This may look like C code, but it is really -*- C++ -*-
  30. /* 
  31. Copyright (C) 1988 Free Software Foundation
  32.     written by Doug Lea (dl@@rocky.oswego.edu)
  33.  
  34. This file is part of GNU CC.
  35.  
  36. GNU CC is distributed in the hope that it will be useful,
  37. but WITHOUT ANY WARRANTY.  No author or distributor
  38. accepts responsibility to anyone for the consequences of using it
  39. or for whether it serves any particular purpose or works at all,
  40. unless he says so in writing.  Refer to the GNU CC General Public
  41. License for full details.
  42.  
  43. Everyone is granted permission to copy, modify and redistribute
  44. GNU CC, but only under the conditions described in the
  45. GNU CC General Public License.   A copy of this license is
  46. supposed to have been given to you along with GNU CC so you
  47. can know your rights and responsibilities.  It should be in a
  48. file named COPYING.  Among other things, the copyright notice
  49. and this notice must be preserved on all copies.  
  50. */
  51.  
  52.  
  53. #ifndef _TimeSchedulerSplayPQ_h
  54. #define _TimeSchedulerSplayPQ_h 1
  55.  
  56. #include <TimeSchedulerPQ.h>
  57.  
  58. #ifndef _TimeSchedulerSplayNode
  59. #define _TimeSchedulerSplayNode 1
  60.  
  61. struct TimeSchedulerSplayNode
  62. {
  63.   TimeSchedulerSplayNode*   lt;
  64.   TimeSchedulerSplayNode*   rt;
  65.   TimeSchedulerSplayNode*   par;
  66.   TimeScheduler             item;
  67.                   TimeSchedulerSplayNode(TimeScheduler& h, TimeSchedulerSplayNode* l=0, TimeSchedulerSplayNode* r=0);
  68.                   ~TimeSchedulerSplayNode();
  69. };
  70.  
  71.  
  72. inline TimeSchedulerSplayNode::TimeSchedulerSplayNode(TimeScheduler& h, TimeSchedulerSplayNode* l=0, TimeSchedulerSplayNode* r=0)
  73. {
  74.   item = h;
  75.   lt = l;
  76.   rt = r;
  77.   par = 0;
  78. }
  79.  
  80. inline TimeSchedulerSplayNode::~TimeSchedulerSplayNode() {}
  81.  
  82. typedef TimeSchedulerSplayNode* TimeSchedulerSplayNodePtr;
  83.  
  84. #endif
  85.  
  86. class TimeSchedulerSplayPQ : public TimeSchedulerPQ
  87. {
  88. protected:
  89.   TimeSchedulerSplayNode*   root;
  90.  
  91.   TimeSchedulerSplayNode*   leftmost();
  92.   TimeSchedulerSplayNode*   rightmost();
  93.   TimeSchedulerSplayNode*   pred(TimeSchedulerSplayNode* t);
  94.   TimeSchedulerSplayNode*   succ(TimeSchedulerSplayNode* t);
  95.   void            _kill(TimeSchedulerSplayNode* t);
  96.   TimeSchedulerSplayNode*   _copy(TimeSchedulerSplayNode* t);
  97.  
  98. public:
  99.                   TimeSchedulerSplayPQ();
  100.                   TimeSchedulerSplayPQ(TimeSchedulerSplayPQ& a);
  101.                   ~TimeSchedulerSplayPQ();
  102.  
  103.   Pix           enq(TimeScheduler& item);
  104.   TimeScheduler           deq(); 
  105.  
  106.   TimeScheduler&          front();
  107.   void          del_front();
  108.  
  109.   int           contains(TimeScheduler& item);
  110.  
  111.   void          clear(); 
  112.  
  113.   Pix           first(); 
  114.   Pix           last(); 
  115.   void          next(Pix& i);
  116.   void          prev(Pix& i);
  117.   TimeScheduler&          operator () (Pix i);
  118.   void          del(Pix i);
  119.   Pix           seek(TimeScheduler& item);
  120.  
  121.   int           OK();                    // rep invariant
  122. };
  123.  
  124. inline TimeSchedulerSplayPQ::~TimeSchedulerSplayPQ()
  125. {
  126.   _kill(root);
  127. }
  128.  
  129. inline TimeSchedulerSplayPQ::TimeSchedulerSplayPQ()
  130. {
  131.   root = 0;
  132.   count = 0;
  133. }
  134.  
  135. inline TimeSchedulerSplayPQ::TimeSchedulerSplayPQ(TimeSchedulerSplayPQ& b)
  136. {
  137.   count = b.count;
  138.   root = _copy(b.root);
  139. }
  140.  
  141. inline Pix TimeSchedulerSplayPQ::first()
  142. {
  143.   return Pix(leftmost());
  144. }
  145.  
  146. inline Pix TimeSchedulerSplayPQ::last()
  147. {
  148.   return Pix(rightmost());
  149. }
  150.  
  151. inline void TimeSchedulerSplayPQ::next(Pix& i)
  152. {
  153.   if (i != 0) i = Pix(succ((TimeSchedulerSplayNode*)i));
  154. }
  155.  
  156. inline void TimeSchedulerSplayPQ::prev(Pix& i)
  157. {
  158.   if (i != 0) i = Pix(pred((TimeSchedulerSplayNode*)i));
  159. }
  160.  
  161. inline TimeScheduler& TimeSchedulerSplayPQ::operator () (Pix i)
  162. {
  163.   if (i == 0) error("null Pix");
  164.   return ((TimeSchedulerSplayNode*)i)->item;
  165. }
  166.  
  167. inline void TimeSchedulerSplayPQ::clear()
  168. {
  169.   _kill(root);
  170.   count = 0;
  171.   root = 0;
  172. }
  173.  
  174. inline int TimeSchedulerSplayPQ::contains(TimeScheduler& key)
  175. {
  176.   return seek(key) != 0;
  177. }
  178.  
  179.  
  180. #endif
  181. @
  182.  
  183.  
  184. 3.2
  185. log
  186. @Start using Gnu library heaps for schedulers
  187. @
  188. text
  189. @d28 1
  190. a28 1
  191. #include "TimeSchedulerPQ.h"
  192. @
  193.